The present invention relates to error correcting coding and decoding. More specifically it relates to correcting symbols in error in cyclic codes.
Error correction of digital codes is widely used in telecommunications and in transfer of information such as reading of data from storage media such as optical disks. Detection of errors can take place by analyzing symbols that were added to the information symbols during coding. The relation between information symbols and the added coding symbols is determined by a rule. If after reception of the symbols such relation between the symbols as provided by the rule no longer holds, it can be determined that some of the symbols are different or in error compared to the original symbols. Such a relationship may be a parity rule or a syndrome relationship. If the errors do not exceed a certain number within a defined number of symbols it is possible to identify and correct these errors. Known methods of creating error correcting codes and correction of errors are provided by BCH codes and the related Reed-Solomon (RS) codes. These are known as (p,k) codes having codewords of p n-valued symbols of which k symbols are information symbols.
Error-correction in (p,k) codes usually involves locating symbols in error, determining the magnitude of an error and determining the correct value or state of a symbol. Calculations in (p,k) codes such as RS codes can be time and/or resource consuming and may add to a coding latency.
The inventor has described in earlier patent applications how after determining an error location in a codeword one can determine the correct symbol value without first determining an error magnitude or error value as it is also called. Also described in earlier patent applications is the up-and-down approach in determining intermediate coding states. These aspects are described in U.S. Provisional Patent Application No. 60/807,087, filed Jul. 12, 2006, and U.S. Provisional Patent Application No. 60/821,980 filed Aug. 10, 2006 which are both incorporated herein by reference in their entirety. U.S. patent application Ser. No. 11/739,189 filed Apr. 26, 2007 and U.S. patent application Ser. No. 11/743,893 filed May 3, 2007 and U.S. patent application Ser. No. 11/775,963 filed on Jul. 11, 2007 are also incorporated herein by reference in their entirety.
For instance U.S. patent application Ser. No. 11/775,963 requires the creation of a state difference matrix created from assumed symbols in error. One may write all up and down states as a state difference vector. One may further put in the position of a vector a 0 when corresponding states are identical and a 1 when corresponding states are different. One can then create a matrix formed of state difference vectors for specific error combinations. Furthermore, the vectors will be put in descending order of number of 0s in the matrix. One can easily create the vectors by inserting errors in codewords and determining the state difference vectors. A representative state difference matrix is shown in FIG. 24 of this patent application. This method can be effective in detecting errors in relatively short codewords. However, applying it to long words may create a very large matrix.
Thus, one of the most time and/or resource consuming efforts in error correction of symbols in error in a Reed-Solomon codeword, especially in a long code-word, is the determination of an error location. This creates a bottleneck in high speed decoding and error correction of received codewords in error in applications that involve high speed data transfer.
Accordingly novel methods and apparatus that can locate and correct a symbol in error in a faster or easier way are required.